import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Leetcode969 {
    public static void main(String[] args) {
        System.out.println(pancakeSort(new int[]{3, 2, 4, 1}));
    }

    public static List<Integer> pancakeSort(int[] arr) {
        List<Integer> res = new ArrayList<>();
        int handIndex = arr.length;
        while (handIndex > 0) {
            int maxIndex = getArrayMaxIndex(arr, handIndex);
            while (maxIndex == handIndex - 1) {
                handIndex--;
                maxIndex = getArrayMaxIndex(arr, handIndex);
            }

            if (maxIndex + 1 == 0) {
                return res;
            }

            res.add(maxIndex + 1);
            reverse(arr, maxIndex);
            res.add(handIndex);
            reverse(arr, handIndex - 1);
            handIndex--;
        }

        return res;
    }

    private static int getArrayMaxIndex(int[] arr, int endIndex) {
        int maxNumber = Integer.MIN_VALUE;
        int maxNumberIndex = -1;
        for (int i = 0; i < endIndex; i++) {
            if (arr[i] > maxNumber) {
                maxNumber = arr[i];
                maxNumberIndex = i;
            }
        }

        return maxNumberIndex;
    }

    public static void reverse(int[] arr, int end) {
        for (int i = 0, j = end; i < j; i++, j--) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

}
